package DataStructure.binarySearch;

/**
 * @Author: Dijah
 * @Date: 2023/3/15 10:58
 * @Desc: https://labuladong.github.io/algo/di-ling-zh-bfe1b/wo-xie-le--3c789/
 * 二分查找
 */
public class demo1 {

    /**
     * 寻找左侧边界的二分搜索
     * @param nums
     * @param target
     * @return
     */
    public static int left_bound(int [] nums,int target){
        int left = 0;
        //注意这里 -1
        int right = nums.length- 1;
        while (left <= right){
            int mid = left + (right - left) / 2;
            if(nums[mid] < target){
                left = mid + 1;
            }else if(nums[mid] > target){
                right = mid - 1;
            } else if(nums[mid] == target){
                right = mid - 1;
            }
        }
        // 判断 target 是否存在于 nums 中
        // 如果越界，target 肯定不存在，返回 -1
        if(left < 0 || left >= nums.length){
            return -1;
        }
        return nums[left] == target ? left : -1;
    }

    /**
     * 寻找右侧边界
     * @param nums
     * @param target
     * @return
     */
    public static int right_bound(int [] nums,int target){
        int left = 0;
        int right = nums.length - 1;
        while (left <= right){
            int mid = left + (right - left) / 2;
            if(nums[mid] < target){
                left = mid + 1;
            }else if(nums[mid] > target){
                right = mid - 1;
            }else if(nums[mid] == target){
                //收缩左边界
                left = mid + 1;
            }
        }
        //left-1 越界
        if(left - 1 < 0 || left - 1 >= nums.length){
            return -1;
        }
        return nums[left - 1] == target ? left - 1 : -1;
    }

    public static void main(String[] args) {
        int [] nums = {1,3,4,5,6,8,7,12,34};
        int target = 6;
        int i = left_bound(nums, target);
        System.out.println(i);
        int i1 = right_bound(nums, target);

        System.out.println(i1);
    }
}
